package company.qihu360;

import java.util.Scanner;

/**
 * @author briarbear
 * @blog https://briarbear.github.io
 * @date 2018-09-17 20:05
 */
public class Q1 {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            int q = scanner.nextInt();  //q组询问
            for (int i = 0; i < q; i++) {
                int k = scanner.nextInt();  // 进制数
                long l = scanner.nextLong();
                long r = scanner.nextLong();
                System.out.println(helper(k, l, r));
            }
        }
    }



    public static long helper(int k,long l,long r){

        long temp = 0;
        int n = (int) (Math.log(r) / Math.log(k));
        for (int i = 0; i <= n; i++) {
            temp = temp * k + k - 1;
        }

        while ( temp > r){
            temp = (temp - k +1) / k;
        }
        return temp;
    }
}
